import java.util.Arrays;

/**
 * 338. 比特位计数
 */
public class Solution_338 {
    /**
     * 方法三：动态规划-最高有效位
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            // i 是 2 的整数次幂，当且仅当 y & (y−1) = 0
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            ans[i] = ans[i - highBit] + 1;
        }
        return ans;
    }

    /**
     * 方法二：直接计算
     * <p>
     * 时间复杂度：O(n*sizeof(integer))
     * <p>
     * 空间复杂度：O(1)
     */
    public int[] countBits2(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            ans[i] = countOnes(i);
        }
        return ans;
    }

    /**
     * 计算给定整数 x 的二进制中 1 的个数
     */
    private int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            // 按位与运算 & 的性质：
            // x = x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0
            x &= (x - 1);
            ones++;
        }
        return ones;
    }

    /**
     * 方法一：Java 内置方法
     */
    public int[] countBits1(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            ans[i] = Integer.bitCount(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution_338 solution = new Solution_338();
        int[] ans = solution.countBits(5);
        System.out.println(Arrays.toString(ans));
    }
}
